package BinaryTree;
/**
 * 最大二叉树
 */
import BinaryTree.init.TreeNode;

public class lc654 {

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return constructMaximumBinaryTree(nums, 0, nums.length);
    }
    
    public TreeNode constructMaximumBinaryTree(int[] nums, int leftIndex, int rightIndex) {
        if (rightIndex - leftIndex < 1) return null;
        if (rightIndex - leftIndex == 1) return new TreeNode(nums[leftIndex]);
        int maxIndex = leftIndex;
        int maxValue = nums[maxIndex];
        for (int i = leftIndex + 1; i < rightIndex; i++) {
            if (nums[i] > maxValue) {
                maxIndex = i;
                maxValue = nums[i];
            }
        }
        TreeNode root = new TreeNode(maxValue);
        root.left = constructMaximumBinaryTree(nums, leftIndex, maxIndex);
        root.right = constructMaximumBinaryTree(nums, maxIndex + 1, rightIndex);
        return root;
    }

}
